//https://leetcode.cn/problems/number-of-subarrays-with-bounded-maximum/
package codeRandomThoughts.Test795区间子数组个数;

//动态规划
public class Solution {
    public int numSubarrayBoundedMax(int[] nums, int left, int right) {
        //dp[i]:以nums[i]为最后一个元素的满足条件的子数组的个数
        int[] dp = new int[nums.length];

        //初始化
        if (nums[0] >= left && nums[0] <= right) {
            dp[0] = 1;
        }

        int result = 0;

        //记录上一次出现的>=left的位置
        //初始化为-1 如果0满足就初始化为0
        int k = nums[0] >= left ? 0 : -1;

        for (int i = 1; i < nums.length; i++) {
            if (nums[i] > right) {
                dp[i] = 0;
            } else if (nums[i] < left) {
                dp[i] = dp[i - 1];
            } else {
                dp[i] = dp[i - 1] + (i - k);
            }

            //更新k
            if (nums[i] >= left) k = i;
        }

        for (int i = 0; i < dp.length; i++) {
            result += dp[i];
        }

        return result;
    }
}
